package 动态规划;

import java.util.Arrays;

/**
 * @author TTDB
 * @create 2025/9/23
 */
public class numSquares {
    // 完全平方数,从小开始累计
     public int numSquares(int n)
    {
         int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
         for(int i = 1; i <= n; i++){
             for(int j = 1; j * j <= i; j++){
                 dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
             }
         }
         return dp[n];
    }
}
